import java.util.ArrayList;
import java.util.List;

//子集的第二种解法：收集所有的结点
public class SubsetTest2 {
    static List<Integer> path;//用来记录一次的子集
    static List<List<Integer>> ret;//用来记录总的子集情况

    public static void permute(int[] nums, int deep) {
        //1.初始化
        path = new ArrayList<>();
        ret = new ArrayList<>();
        //2.回溯的核心
        dfs(nums, deep);
    }

    //nums：需要计算子集的数组
    //deep：表示当前来到树的第几层也是容量的意思
    public static void dfs(int nums[], int deep) {
        //因为每一个结点都是我需要的结果，所以每一个结点都要收集
        ret.add(new ArrayList<>(path));

        //回溯开始
        //这里必须从deep开始，表示在nums数组中的第几位开始
        //只有这样，才不会导致重复选取
        for (int i = deep; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1);
            //恢复现场
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        permute(nums, 0);
        for (int i = 0; i < ret.size(); i++) {
            System.out.println(ret.get(i));
        }
    }
}
